238. Product of Array Except Self
Medium

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

 

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

 

Constraints:

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Accepted
797,598
Submissions
1,294,451
Seen this question in a real interview before?
Related Topics

Average Rating: 4.65 (285 votes)

Premium

Solution

From the looks of it, this seems like a simple enough problem to solve in linear time and space. We can simply take the product of all the elements in the given array and then, for each of the elements xx of the array, we can simply find product of array except self value by dividing the product by xx.

Doing this for each of the elements would solve the problem. However, there's a note in the problem which says that we are not allowed to use division operation. That makes solving this problem a bit harder.


Approach 1: Left and Right product lists

It's much easier to build an intuition for solving this problem without division once you visualize how the different products except self look like for each of the elements. So, let's take a look at an example array and the different products.

Looking at the figure about we can figure another way of computing those different product values.

Instead of dividing the product of all the numbers in the array by the number at a given index to get the corresponding product, we can make use of the product of all the numbers to the left and all the numbers to the right of the index. Multiplying these two individual products would give us the desired result as well.

For every given index, ii, we will make use of the product of all the numbers to the left of it and multiply it by the product of all the numbers to the right. This will give us the product of all the numbers except the one at the given index ii. Let's look at a formal algorithm describing this idea more concretely.

Algorithm

  1. Initialize two empty arrays, L and R where for a given index i, L[i] would contain the product of all the numbers to the left of i and R[i] would contain the product of all the numbers to the right of i.
  2. We would need two different loops to fill in values for the two arrays. For the array L, L[0]L[0] would be 1 since there are no elements to the left of the first element. For the rest of the elements, we simply use L[i]=L[i1]nums[i1]L[i] = L[i - 1] * nums[i - 1]. Remember that L[i] represents product of all the elements to the left of element at index i.
  3. For the other array, we do the same thing but in reverse i.e. we start with the initial value of 1 in R[length1]R[length - 1] where lengthlength is the number of elements in the array, and keep updating R[i] in reverse. Essentially, R[i]=R[i+1]nums[i+1]R[i] = R[i + 1] * nums[i + 1]. Remember that R[i] represents product of all the elements to the right of element at index i.
  4. Once we have the two arrays set up properly, we simply iterate over the input array one element at a time, and for each element at index i, we find the product except self as L[i]R[i]L[i] * R[i].

Let's go over a simple run of the algorithm that clearly depicts the construction of the two intermediate arrays and finally the answer array.

Current
1 / 10

For the given array [4,5,1,8,2][4,5,1,8,2], the L and R arrays would finally be:

Complexity analysis

  • Time complexity : O(N)O(N) where NN represents the number of elements in the input array. We use one iteration to construct the array LL, one to construct the array RR and one last to construct the answeranswer array using LL and RR.
  • Space complexity : O(N)O(N) used up by the two intermediate arrays that we constructed to keep track of product of elements to the left and right.


Approach 2: O(1) space approach

Although the above solution is good enough to solve the problem since we are not using division anymore, there's a follow-up component as well which asks us to solve this using constant space. Understandably so, the output array does not count towards the space complexity. This approach is essentially an extension of the approach above. Basically, we will be using the output array as one of L or R and we will be constructing the other one on the fly. Let's look at the algorithm based on this idea.

Algorithm

  1. Initialize the empty answer array where for a given index i, answer[i] would contain the product of all the numbers to the left of i.
  2. We construct the answer array the same way we constructed the L array in the previous approach. These two algorithms are exactly the same except that we are trying to save up on space.
  3. The only change in this approach is that we don't explicitly build the R array from before. Instead, we simply use a variable to keep track of the running product of elements to the right and we keep updating the answer array by doing answer[i]=answer[i]Ranswer[i] = answer[i] * R. For a given index i, answer[i] contains the product of all the elements to the left and R would contain product of all the elements to the right. We then update R as R=Rnums[i]R = R * nums[i]

Complexity analysis

  • Time complexity : O(N)O(N) where NN represents the number of elements in the input array. We use one iteration to construct the array LL, one to update the array answeranswer.
  • Space complexity : O(1)O(1) since don't use any additional array for our computations. The problem statement mentions that using the answeranswer array doesn't add to the space complexity.

Report Article Issue

Comments: 140
spooja__'s avatar
Read More

How in the world can I ever think of this in an interview

1.8K
Show 50 replies
Reply
Share
Report
anubhakushwaha's avatar
Read More

We can utilize properties of log, if input array is [a, b, c, d] then
precalculated_val = log(a* b* c* d) = log(a) + log(b) + log(c) + log(d)
So for output array it would be { antilog [precalculated_val - log(arr[i])] }

196
Show 11 replies
Reply
Share
Report
mike_zamini's avatar
Read More

Don't you think that the second approach is NOT in O(1) space complexity? We are still using ONE intermediate array (answer) to make the L array. So it is O(N), right?

133
Show 17 replies
Reply
Share
Report
stalasila's avatar
Read More

Good One !!!

29
Reply
Share
Report
renyj1991's avatar
Read More

So what is the purpose of this kind of problem? I give up...

18
Show 1 reply
Reply
Share
Report
mhelvens's avatar
Read More

There's more to the simple solution using division than this article suggests. I challenge people to try to implement that solution. I predict that most will not get it right on their first try.
(If you'd like to try, refrain from opening / reading the replies to this comment.)

29
Show 11 replies
Reply
Share
Report
al-abbasi's avatar
Read More

It's slightly quicker if you don't use reversed (faster than 99% of submissions)

class Solution(object):
def productExceptSelf(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    answer = [1]*len(nums)
    answer[0] = 1
    for i in range(1, len(nums)):
        answer[i] = answer[i-1] * nums[i-1]
    rightProduct = 1
    for i in range(len(nums)-1, -1, -1):
        answer[i] = answer[i] * rightProduct
        rightProduct *= nums[i]
    return answer

14
Show 2 replies
Reply
Share
Report
Pkoiralap's avatar
Read More

I did it this way:

  1. If there is a single zero in the list, every other elements will be zero expect for that

  2. If there are more than one zero in the list, every element will be zero

  3. Else we calculate prod = product of every element, answer is product divided by individual items

    def productExceptSelf(self, nums):
       """
       :type nums: List[int]
       :rtype: List[int]
       """
       zero_loc = -1
       prod = 1
       for i, num in enumerate(nums):
           if num == 0:
               if zero_loc == -1:
                   zero_loc = i
               else:
                 zero_loc = "multiple"
           else:
               prod *= num
     
       if zero_loc == "multiple":
           return [0 for x in nums]
       elif zero_loc != -1:
           return [0 if i != zero_loc else prod for i, num in enumerate(nums)]
       else:
           return [prod/x for x in nums]

24
Show 6 replies
Reply
Share
Report
stanislaw89's avatar
Read More

The description should contain a note that there are not 0 in the array, otherwise, the solution above won't work.

11
Show 2 replies
Reply
Share
Report
Hogwarts's avatar
Read More

Is the space complexity of the second approach O(1)? I think it's O(n)

11
Show 2 replies
Reply
Share
Report
Success
Details
Runtime: 20 ms, faster than 84.35% of C++ online submissions for Product of Array Except Self.
Memory Usage: 25.2 MB, less than 13.02% of C++ online submissions for Product of Array Except Self.
Time Submitted
Status
Runtime
Memory
Language
06/15/2021 08:50Accepted20 ms25.2 MBcpp
06/03/2021 19:14Accepted20 ms25 MBcpp
03/05/2021 08:50Accepted28 ms24 MBcpp
05/22/2020 09:05Accepted28 ms16 MBcpp
05/22/2020 08:58Accepted32 ms16.1 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.